package com.company.ljh.medium;

import java.util.HashMap;
import java.util.Map;

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2024/4/7 15:04
 * @version:1.0
 */
public class Lru缓存 {
    public static void main(String[] args) {
        Lru缓存 lruCache = new Lru缓存(2);
        lruCache.put(2, 1);
        lruCache.put(3, 2);
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(2));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(2));
        lruCache.put(4, 4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));


        //

    }

    class Node {
        //双向链表
        int key;
        int value;
        Node prev;
        Node next;
    }

    Map<Integer, Node> lruMap;
    Node head;
    Node tail;
    int size;
    int capacity;

    public Lru缓存(int capacity) {
        lruMap = new HashMap(capacity);
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = lruMap.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = lruMap.get(key);
        //不重复的情况
        if (node == null) {
            Node newNode = new Node();
            newNode.key = key;
            newNode.value = value;
            newNode.next = head;
            lruMap.put(key, newNode);
            //将当前节点设置为尾节点（考虑头节点为空的情况）
            if (head != null) {
                head.prev = newNode;
            }
            head = newNode;
            //尾节点为空，将第一个节点初始化为尾节点
            if (tail == null) {
                tail = newNode;
            }
            size++;

        } else {
            node.value = value;
            moveToHead(node);
        }
        if (size > capacity) {
            lruMap.remove(tail.key);
            tail.prev.next = null;
            tail = tail.prev;
            size--;
        }

    }

    public void moveToHead(Node node) {
        //当前节点为头节点时，不移动
        if (node == head){
            return;
        }

        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        //当前节点为尾节点时，尾节点设置为当前节点的前一个节点
        if (tail == node && node.prev != null) {
            tail = node.prev;
        }

        node.prev = null;
        node.next = head;
        head.prev = node;
        head = node;
    }
}
